As an aid to understanding the prior art, a schematic representation of a multi-dimensional, parallel computer network is shown in FIG. 1. Each of boxes 0-8 is a data processing site called a node, which nodes may be homogeneous or heterogeneous. Each of nodes 0-8 must be able to receive data blocks from other nodes and send data blocks to other nodes. Data links interconnect the nodes in either a regular or irregular pattern. In FIG. 1, lines 100-111 between nodes 0-8 schematically represent such data links.
The prior art indicates many possible ways of finding message routes between source and destination nodes. In general, all such ways assume that a message always tries to make progress towards the destination node. In practice, the search paths established during the time the network attempts to route a message from a source node to a destination node is unimportant. All that the source node generally needs to be informed of is whether a path was found over which to transmit the message. If no path is found, the source node is only concerned with the maximum progress the message made through the network in order to determine a proper recovery action.
In FIG. 2, an exemplary search tree is illustrated. Assume node 0 in FIG. 1 is to send a message to node 8 using redundant paths in order to protect against network congestion and faults. Several parallel paths exist between these two nodes, as shown in FIG. 2. Initially, a message is sent from node 0 to node 1 using link 100 (see FIG. 1). In parallel, node 0 also sends the message to node 3 using link 106. After arriving at node 1, the message is sent to node 2 using link 101 and to node 4 using link 107. Similarly, node 3 passes the message onto node 4, using link 102 and to node 6 using link 109. A repetition of this process enables all possible paths from node 0 to node 8 to be found. This search technique creates a search tree of paths, as illustrated in FIG. 2. Node 0 is at the root of the tree since it is the source node. Nodes 1 and 3 are children of node 0 because node 0 can use either of them as part of a path to node 8. Node 1's children are nodes 2 and 4. Similarly, node 3's children are nodes 4 and 6. Node 8 is the ultimate destination node of each search branch.
There are many techniques for network implementation which provide methods for handling contention between nodes. For instance, in U.S. Pat. No. 4,814,979 to Neches, all messages occupy places in a coherent priority scheme and are transferred in contending groups, with assigned priority, on the network. The relative message priorities are then employed to determine which message advances through the network at the cost of other messages. In U.S. Pat. No. 4,847,837 to Morales et al., redundant data paths are employed with a master switch deciding which one of the redundant paths is to be employed for transmitting and receiving messages between nodes.
In U.S. Pat. 4,766,534 to DeBenedictis a message-passing, parallel processing system between a plurality of nodes is described. Messages are passed between processing nodes in fixed size blocks and only when input buffers are empty is such a message enabled to pass. Flow control of the network is thus self-regulating and deadlocks are avoided. U.S. Pat. Nos. 3,623,067 to Deal, Jr. et al. and 4,545,013 to Lyon et al. show multi-dimensional processing systems wherein system status is employed to influence message transmissions. In the Deal, Jr. et al. patent, parallel connected network lines are employed to enable processors to report to a master system and indicate the status of a particular transaction. The master system then uses the status indication to enable further message transmissions. In Lyon et al., the processing system automatically monitors the status of the network and each of its component units, by periodically polling the network for changes of status and updating the information in a network configuration table.
In many networks, a message is positively acknowledged when it reaches a destination node, with an acknowledgement being transmitted back along the path used to transmit the message. Thus, a source node enqueues its message into the network and starts a countdown timer. If the positive acknowledgement is received before the timer expires, the message transmission is considered successful. If the timer expires before an acknowledgement is received, the message transmission is considered a failure and the message is resent. The problem with this scheme is that the source node only knows if the message transmission succeeded or failed. Message failure may have been caused by a variety of reasons, including network congestion, broken links, transmission errors, node errors etc. Since the source node does not know the cause of the failure or the maximum message progress, its only option is to attempt to resend the message or abort the message.
Some single-dimensional (one path) networks return specific status words when a message transfer has failed. Such a message does not scale to multi-dimensional networks where multiple paths fail. More specifically, where multiple paths fail, the source node must process every error that occurs on every search path, thereby requiring considerable allocation of processing time to unsuccessful message transmission tries. One technique for refining this scheme is to allow intermediate nodes to accumulate error reports and pass only the most severe error report to its parent node. While this scheme reduces the acknowledgement message traffic, the source node is only informed of the most severe error occurring on any search branch without any information regarding message progress being reported.
Accordingly, it is an object of this invention to provide a message progress reporting system for a multi-dimensional, computer network which minimizes the amount of network bandwidth required for progress reporting.
It is another object of this invention to provide a system for message progress reporting in a parallel computing network which is adapted to accommodate multiple search trees passing through any node and to be adaptable to any width or depth of a search tree within a network.
It is yet another object of this invention to provide a system for reporting message progress in a parallel computing network wherein only a single status indication between nodes is employed to encapsulate the maximum progress of the message.
A still further object of this invention is to provide a system for reporting message progress in a parallel computing network which can operate in a network where each message transfer is acknowledged or in a network wherein only negative acknowledgements (i.e. error reports ) occur.